package com.uyong.study.algorithm.sort;

import java.util.Arrays;

/**
 * 计数排序O(n),非原地O(n),稳定
 * 
 * @author gonggy
 * @since 2019-01-30
 */
public class CountingSort implements ISort {

	@Override
	public void sort(int[] data) {
		if (data.length <= 1) {
			return;
		}
		// 1.确定数组中最大值，用于确定数据范围
		int max = Arrays.stream(data).max().getAsInt();

		// 2.申请一个计数数组，用于统计每个数据出现的次数
		int[] count = new int[max + 1];

		// 3.统计每个数据出现的次数
		for (int i = 0; i < data.length; i++) {
			count[data[i]]++;
		}

		// 4.累加计数数组，每一项为当前项和前面各项的和
		for (int i = 1; i < count.length; i++) {
			count[i] += count[i - 1];
		}

		// 5.排序过程
		int[] sorted = new int[data.length];
		// 从最后一位开始排序，保证稳定性，如果从第一位开始，则算法不稳定
		for (int i = data.length - 1; i >= 0; i--) {
			int elem = data[i]; // 取待排序的元素
			int index = count[elem] - 1; // 待排序元素在有序数组中的序号
			sorted[index] = elem; // 将元素放入有序数组中
			count[elem]--; // 修正计数
		}

		// 拷贝结果到原数组中
		System.arraycopy(sorted, 0, data, 0, data.length);
	}

}
